package 腾讯;

import java.util.*;

/**
 * @author zhangmin
 * @create 2022-04-24 19:59
 */
public class Main2 {
    public int getNumber (int[] a) {
        // write code here
        int n=a.length;
        //求出n以内的所有质数并记录下来
        Set<Integer> primes=new HashSet<>();
        primes.add(2);
        for (int i = 3; i <=n ; i+=2) {
            int flag=0;
            for (int j = 2; j < Math.sqrt(i); j++) {
                if (i%j==0){
                    flag=1;
                    break;
                }
            }
            if (flag==0){
                primes.add(i);
            }
        }
        //标记删除元素后的下标位置，用双指针，直接将留下的元素向前移动
        int len=n-1;
        while ((len>=1)){
            //在[0-len]之间是保留的元素
            int i=0;
            for (int j = 0; j <= len; j++) {
                if (!primes.contains(j+1)){
                    //需要删除的
                    continue;
                }else {
                    a[i]=a[j];
                    i++;
                }
            }
            len=i-1;
        }
        return a[0];
    }

    public static void main(String[] args) {
        Main2 obj=new Main2();
        int[] a={1,2,3,4};
        System.out.println(obj.getNumber(a));
    }
}
